﻿#pragma once
#include "Index.h"

/**
 * 拼车.
 * https://leetcode.cn/problems/car-pooling/
 * 数组 差分 排序 模拟 堆
 *
 * 车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）
 * 给定整数 capacity 和一个数组 trips ,  trip[i] = [numPassengersi, fromi, toi] 
 * 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。
 * 这些位置是从汽车的初始位置向东的公里数。
 * 当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。
 */
class CarPooling
{
public:
	bool carPooling(std::vector<std::vector<int>>& trips, int capacity)
	{
		if (trips.empty() || capacity <= 0)
			return false;

		memset(&diff.front(), 0, sizeof(int) * diff.size());
		const int tripLen = diff.size();
		int useTripLen = 0;

		for (const auto& info : trips)
		{
			const int passengerCount = info[0];
			const int sta = info[1];
			const int fin = info[2];
			useTripLen = std::max<>(fin, useTripLen);

			//为区间 [sta,fin)整体加上passengerCount,注意下车和上车同一位置的情况，先下车再上车
			diff[sta] += passengerCount;
			if (fin < tripLen)
				diff[fin] -= passengerCount;
		}

		int maxPassengerCount = 0;
		for (int i = 0; i <= useTripLen; ++i)
		{
			maxPassengerCount += diff[i];
			if (maxPassengerCount > capacity)
				return false;
		}
		return true;
	}
private:
	static std::vector<int> diff;
};
std::vector<int> CarPooling::diff(1001, 0);